/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-k-sorted-lists
   @Language: C++
   @Datetime: 16-02-09 08:17
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */


// Method 1, using merge two sorted lists, Time 127ms
class Solution {
	ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
		// H is the virtual head for merged list
		ListNode H(-1), *p;
		for(p=&H; l1 && l2; p=p->next){
			if (l1->val < l2->val){
				p->next = l1;
				l1 = l1->next;
			}
			else{
				p->next = l2;
				l2 = l2->next;
			}
		}
		p->next = (l1 ? l1:l2);
		return H.next;
	}
public:
	/**
	 * @param lists: a list of ListNode
	 * @return: The head of one sorted list.
	 */
	/** Tips: merge each two lists to one list
	 * all lists are single list without head node
	 * see problem 16 for details of merge two sorted lists 
	 * Time O(nlogk), Space O(1), n is total nodes of k lists
	 *
	 * two point i and j, which i from 0 to j, and j from end-1 to 0
	 * merge lists[i] and lists[j],and ++i, --j;
	 * when i>=j, rewind i to 0
	 * untill j=0, done
	 * */
	ListNode *mergeKLists(vector<ListNode *> &lists) {
		// write your code here
		if (lists.size() < 1) return NULL;
		for(int i=0, j=lists.size()-1; j; ++i){
			i = (i>=j ? 0:i);
			lists[i] = mergeTwoLists(lists[i],lists[j--]);
		}
		return lists[0];
	}
};


// Method 2, MiniHeap, Time 338ms
class Solution {
	struct Node{
		ListNode *value, *next;
		Node(ListNode *val, ListNode *n):value(val),next(n){}
		bool operator<(const Node &a)const{
			return value->val > a.value->val;   // mini heap
		}
	};
public:
	/**
	 * @param lists: a list of ListNode
	 * @return: The head of one sorted list.
	 */
	ListNode *mergeKLists(vector<ListNode *> &lists) {
		// write your code here
		ListNode H;
		priority_queue<Node> heap;  //mini heap
		for(const auto &p:lists)
			if(p) heap.push(Node(p,p->next));
		for(ListNode *p=&H; heap.size(); heap.pop()){
			const auto &n=heap.top();
			p=p->next=n.value;
			if(n.next) heap.push(Node(n.next,n.next->next));
		}
		return H.next;
	}
};

